package week07

import "math"

// 1334. 阈值距离内邻居最少的城市
// https://leetcode-cn.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
	var graph = make([][]int, n)
	for i := range graph {
		graph[i] = make([]int, n)
		for j := range graph[i] {
			graph[i][j] = math.MaxInt32
		}
		graph[i][i] = 0
	}
	for _, edge := range edges {
		var x, y, z = edge[0], edge[1], edge[2]
		graph[x][y] = z
		graph[y][x] = z
	}
	// Floyd 算法
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if graph[i][k] == math.MaxInt32 || graph[k][j] == math.MaxInt32 {
					continue
				}
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
			}
		}
	}
	var ansCount = n
	var ans = 0
	for i := 0; i < n; i++ {
		var count = 0
		for j := 0; j < n; j++ {
			if i != j && graph[i][j] <= distanceThreshold {
				count++
			}
		}
		if ansCount >= count {
			ansCount = count
			ans = i
		}
	}
	return ans
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}